Méthodes par différences temporelles n-Step (n-step TD Methods)

2. Prédiction avec les méthodes TD n-step

2.1. Formalisme de la méthode

Nous avons vu en introduction que l'idée des méthodes n-step est d'unifier les méthodes de Monte-Carlo et la méthode TD(0) à un pas. Mais quel est l'espace qui sépare ces deux méthodes ?

Considérons le problème d'évaluer une fonction des valeurs des état $V_\pi$ à partir d'épisodes générés à l'aide d'une stratégie $\pi$. Les méthodes de Monte-Carlo effectuent une mise à jour des états de l'environnement en se basant sur l'ensemble des revenus obtenus jusqu'à la fin d'un épisode. D'un autre coté, les mises à jour réalisées par la méthode TD(0) sont faites directement sur la récompense qui suit un état.

Une Solution intermédiaire serait donc de réaliser des mises à jour à partir d'un ensemble de récompenses comprises entre ces deux extrêmes : c'est-à-dire entre plus d'une récompense et l'ensemble de celles obtenues sur un épisode complet (moins une). Par exemple, une mise à jour à deux pas pourra être réalisée sur les deux premières récompenses obtenues après un état, c'est-à-dire deux pas plus tard.

Ces méthodes, qui utilisent plusieurs pas pour les mises à jour, sont des méthodes d'apprentissage par différentes temporelles parce que les premiers états rencontrés sont modifiés en fonction des états suivants.

De manière plus formelle, nous savons que la méthode de Monte-Carlo calcule la valeur d'un état $V_\pi(S_t)$ à l'aide du revenu global (qui est la cible dans la méthode de Monte-Carlo):

$${G_t} = {R_{t + 1}} + \gamma {R_{t + 2}} + {\gamma ^2}{R_{t + 3}} + ... + {\gamma ^{T - t - 1}}{R_T}$$

Alors que dans la méthode de Monte-Carlo ce revenu est la cible, dans la méthode TD(0), la cible est exprimée à l'aide de la première récompense qui suit l'état $S_t$ et d'une proportion de l'estimation de la valeur de l'état suivant $S_{t+1}$:

$${G_{t:t + 1}} = {R_{t + 1}} + \gamma {V_t}\left( {{S_{t + 1}}} \right)$$

L'indice dans l'expression ${G_{t:t + 1}}$ précise ici que le revenu est tronqué entre l'instant $t$ et l'instant $(t+1)$.

Pour une méthode à deux pas, la cible serait :

$${G_{t:t + 2}} = {R_{t + 1}} + \gamma {R_{t + 2}} + {\gamma ^2}{V_{t + 1}}\left( {{S_{t + 2}}} \right)$$

De manière similaire, pour une méthode à n-step, la cible serait donc:

$${G_{t:t + n}} = {R_{t + 1}} + \gamma {R_{t + 2}} + {\gamma ^2}{R_{t + 3}} + ... + {\gamma ^{n - 1}}{R_{t + n}} + {\gamma ^n}{V_{t + n - 1}}\left( {{S_{t + n}}} \right)$$

avec : $n\ge1$ et $0\le t\le T-n$

On peut considérer les revenus obtenus par la méthode n-step comme des approximations tronquées après n pas et ensuite corrigées pour les termes manquants par le facteur ${\gamma ^n}{V_{t + n - 1}}\left( {{S_{t + n}}} \right)$.

2.2. Algorithme de la méthode n-step

On peut remarquer que l'équation précédente ne peut se faire que si les récompenses $R_{t+n}$ dont connues et que la valeur de l'état $V_{t+n-1}$ a été calculé. Cela ne peut se faire qu'au temps $(t+n)$, et donc l'équation récurrente pour calculer la valeur de l'état est de la forme :

$${V_{t + n}}\left( {{S_t}} \right) = {V_{t + n - 1}}\left( {{S_t}} \right) + \alpha \left[ {{G_{t:t + n}} - {V_{t + n - 1}}\left( {{S_t}} \right)} \right]\quad\quad{\rm{ }}0 \le t \le T$$

Les valeurs de tous les autres états restent inchangées: ${V_{t + n}}\left( s \right) = {V_{t + n - 1}}\left( s \right)$, pour tous les états $s\ne S_t$ de l'environnement.

Observons ce que fait l'algorithme pour n=1 et n=2: